/*
* 剪枝方法
* 1.优化搜索顺序：重量从大到小排序
* 2.排除等效冗余：将前K件物品能凑出的重量打表，排序判重，搜索剩下的N-K件物品的选择方式，在表中二分找到不超过W的最大值
* 3.可行性剪枝:不符合规则，直接剪枝
* 4.最优化剪枝：不是最优解，直接剪枝
* 5.记忆化搜索：DP
*/

#include <iostream>
#include <algorithm>
using namespace std;
// #define ONLINE_GUDGE
const int N = 50;
using LL = long long;

int n,w,k;
int G[N];
int weights[1 << 25], cnt = 1; // 能凑出物品的重量 可以凑出重量的个数
int ans;

// 从前向后搜索,找到所有可以拼凑出合法的重量
void dfs1(int u, int s)
{
    if(u == k)
    {
        weights[cnt++] = s;
        return;
    }

    dfs1(u + 1, s); // 不考虑当前物品
    if((LL)s + G[u] <= w)   dfs1(u + 1, s+G[u]); // 当前物品有解则考虑
}

void dfs2(int u, int s) // 枚举第u个物品 当前已组合重量是s
{
    if(u >= n) 
    {
        int l = 0, r = cnt-1;
        while(l < r)
        {
            int mid = (l + r + 1) >> 1;
            if(weights[mid] <= w - s) l = mid;
            else r = mid-1;
        }
        ans = max(ans, weights[l] + s); // 不超过w-s的最大值
        return;
    }
    dfs2(u + 1, s);
    if((LL)s + G[u] <= w)   dfs2(u + 1, s+G[u]); // 当前物品有解则考虑
}

int main()
{
    #ifdef ONLINE_GUDGE

    #else
        freopen("./in.txt", "r", stdin);
    #endif
    ios::sync_with_stdio(0); cin.tie(0);

    cin >> w >> n;
    for(int i = 0; i < n; i++) cin >> G[i];

    sort(G, G + n, greater<int>());


    k = n >> 1;
    dfs1(0, 0);

    sort(weights, weights+cnt);

    cnt = unique(weights, weights+cnt) - weights; // 删掉重复元素有k个
    dfs2(k, 0);

    cout << ans << endl;
    return 0;
}